1. Field of the Invention
The present invention relates to a Viterbi decoder, and particularly to a Viterbi decoder which belongs to a forward error correction method which is used for error controls for digital data transmission.
2. Description of the Prior Art
The Viterbi decoding algorithm was developed in 1967, and is an optimum decoding method for carrying out the maximum likelihood decoding. However, it is difficult to construct its hardware.
The Viterbi decoder is described in: (1) "The Viterbi Algorithm" by G. D. Forney, Proc. IEEE, vol. 61, No. 3, pp 268-278, Mar. 1970; (2) "High Speed Parallel Viterbi Decoding: algorithm and VLSI-architecture" by G. Fettweis and H. Meuer, IEEE Comm., pp 46-55, May 1991; (3) Japanese Patent Laid-open Publication No. Sho-59-19454; and (4) U.S. Pat. No. 5,295,142.
By taking an example of a convolution encoder, a simple Viterbi decoding algorithm will be described below, where the code rate is R=1/2, the constraint length is K=3, and the generating polynomial is as follows: EQU G1=1+X+X.sup.2 EQU G2=1+X.sup.2
As shown in FIG. 1, the convolution encoder includes: a 2-bit shift register 1; and two adders 2 for carrying out modulo-2 additions. Outputs G1 and G2 of the encoder are decided by the state of the content of the shift register and by an input 3. Its outputs over time points are illustrated in the form of a trellis diagram in FIG. 2.
Referring to FIG. 2, the respective states are each joined by two paths, and the Viterbi algorithm selects only one of the two paths, which has a possibility, while the path having-no possibility is discarded. In this manner, the maximum likelihood decoding is carried out. The path thus selected is called a survivor path, and the respective states maintain the information of the survivor paths as much as the decision depth (or truncation depth).
The decoding is carried out by selecting the greatest possibility path from among the survivor paths, and by tracing it back.
When constructing the viterbi decoder, the hardware (e.g., register) which constitutes the state value storing device cannot be enlarged to an infinite size, and an ACS (add-compare-select) arithmetic unit which computes the state values of the respective states repeatedly operates at each hour. Therefore, a data overflow can occur by exceeding the storing capacity of the state value storing device, and therefore, errors can be generated in the decoded output.
In order to prevent such errors, a normalization arithmetic unit for resealing the state values becomes necessary. The Viterbi decoder which has such a function is illustrated in FIG. 3.
Input codes which are inputted into an input terminal 31 are inputted into a branch metric arithmetic unit 32 in which the branch metrics are based on the respective branches 00, 01, 10, and 11.
An ACS (add-compare-select) arithmetic unit 33 receives the output of the branch metric arithmetic unit 32 and the state values of the total time points of the state value storing device 34, so as to compute the survivor paths and the state values. The arithmetic operation of the ACS arithmetic unit 33 is carried out based on the trellis diagram of FIG. 2.
Of the output of the ACS arithmetic unit 33, the information on the survivor paths is stored in a path storing device 37, while the state values are outputted to a normalization arithmetic unit 35 and to a maximum branch metric value detecting device 36.
From the state values received from the ACS arithmetic unit 33, the maximum branch metric value detecting device 36 detects the maximum branch metric value so as to supply the maximum branch metric value to the normalization arithmetic unit 35, while the address of the maximum branch metric value is outputted to a traceback control device 38 so as to control the path storing device 37.
The normalization arithmetic unit 35 subtracts the maximum branch metric values of the maximum branch metric value detecting device 36 from the survivor state values of the respective state of the ACS arithmetic unit 33. The computed result is stored into the state value storing device 34.
Therefore, the state values which are stored in the state value storing device 34 are as follows. That is, the maximum branch metric values (e.g., the smallest state value) are always subtracted from the current time output of the ACS arithmetic unit 33, before storing it. Therefore, a data overflow cannot occur, and one of the state values which are stored in the state value storing device is necessarily zero.
However, in the above described Viterbi decoder, during the time when computing the branch metric for the inputted codes until the time when the new state values are stored in the state value storing device 34, the arithmetic process passes through: the ACS arithmetic unit 33, the maximum branch metric value detecting device 36, and the normalization arithmetic unit 35. Therefore, this poses as an impediment in embodying a high speed Viterbi decoder.
As an example of the conventional techniques for improving the operating speed, a Viterbi decoder was proposed in which, in the normalization process, the maximum branch metric value of the preceding time points is used instead of the maximum branch metric value of the current time, thereby shortening the arithmetic path.
However, in this Viterbi decoder, a relatively complicated hardware is required for detecting the address of the state having the maximum branch metric value. Further, the arithmetic path which is connected from the ACS arithmetic unit to the maximum branch metric value detecting device imposes an impediment all the same.
Another Viterbi decoder was proposed, and in this decoder, the disadvantage of the above described Viterbi decoder was alleviated by normalizing through the use of the maximum branch metric value of the current time. Thus one of the normalized state values which are stored in the state value storing device becomes necessarily zero, thereby improving the operating speed.
However, in this Viterbi decoder, the complicated arithmetic paths become an impediment in the way of improving the operating speed.
If the normalization operation is carried out without using the maximum branch metric value, the maximum branch metric value detecting device can be separated from the arithmetic path consisting of the speed deciding devices such as the ACS arithmetic unit 33, the maximum branch metric value detecting device 36 and the normalization arithmetic unit 35. Generally, the maximum branch metric value detecting device consists of a multi-step comparator, and therefore, the operating speed of the Viterbi decoder can be improved by separating the maximum branch metric value detecting device.
If the received convolution-coded codes are to be decoded by using the Viterbi algorithm, then a synchronization has to be established between the transmitting part and the receiving part. Particularly in an application field in which separate frame synchronizing signals are not used, the Viterbi decoder has to detect the synchronization/non-synchronization for itself based on the received signals, thereby executing the decoding.
The state values increase in time, and the increasing patterns of the state values become different depending on the environment of the transmission path. In the case where a code synchronization is established between the transmitting part and the receiving part, the higher the signal-to-noise ratio Eb/No (where Eb is signal, and No is noise), the smaller the increasing rate of the state values in time becomes. Further, there exists a dominant state in which the state value is far smaller than other state values. On the other hand, the lower the signal-to-noise ratio, the larger the increasing rate of the state values in time. Further, the respective state values are similar to each other. In the case where no synchronization is formed between the transmitting part and the receiving part, the state value increasing patterns are similar to the case where the signal-to-noise ratio is very low.
In the Viterbi decoder which forms a Viterbi algorithm, the state values are stored in a register having a size of 6 or 7 bits, and therefore, in order to prevent a data overflow, a normalization (or resealing) is required.
Generally, in carrying out the normalization, the minimum value of the state values exceeds a threshold value, the threshold value is subtracted from the state values.
FIG. 4 illustrates a conventional Viterbi decoder (U.S. Pat. No. 4,802,174).
In this Viterbi decoder, the frequency of carrying out the normalization is measured for a certain period of time, and if the frequency is higher than a threshold frequency, then it is judged that there is no code synchronization between the transmitting part and the receiving part.
In this Viterbi decoder, of the branch metrics which are computed by a branch metric arithmetic unit 41, the minimum value is extracted, and then, a branch metric normalization is carried out by subtracting the minimum value from the respective branch metrics, thereby improving the accuracy of the detection of the synchronization/non-synchronization. However, this Viterbi decoder needs a separate branch metric normalization arithmetic unit 42, and therefore, the cost for the hardware is increased.
As another example, in the Wei method (U.S. Pat. No. 4,641,327), the number of occurrences d(t) equals non-zero! which is equivalent to the difference between the minimum state value PMmin(t) and the minimum branch metric BMmin(t) is measured for a certain period of time, and the obtained value is compared with a reference value, thereby detecting the synchronization/non-synchronization. However, in this method, a reference value cannot be determined which is capable of precisely detecting the synchronization/non-synchronization without the information on the signal-to-noise ratio.
A Viterbi decoder which improves the Wei method (U.S. Pat. No. 4,641,327) is disclosed in U.S. Pat. No. 5,050,191. In this Viterbi decoder, the synchronization/non-synchronization is detected by means of a measured value of f{d(t)} which is a non-linear function of d(t) which is the difference between the minimum state value PMmin(t) and the minimum branch metric BMmin(t). If d(t)=0, f{d(t)} is accumulated, while if d(t) is non-zero, f{d(t)}=-1 is accumulated. Then the accumulated values are compared with a reference value, thereby detecting the synchronization/non-synchronization. In this method however, there are required an adder for accumulating the values of f{d(t)}, and a comparator for comparing the two reference values. Therefore, this method has the disadvantage that the hardware cost is increased.
The synchronization/non-synchronization detecting method which is proposed in the present invention can be applied to a puncturing convolution encoding technique. The mentioned synchronization/non-synchronization detecting method is as follows. That is, an observation is made for a certain period of time as to whether a traceback is possible from a state having the minimum state value at the immediately preceding time and having the minimum state value at the current time by utilizing the information on the survivor paths, thereby detecting the synchronization/non-synchronization.
The puncturing convolution encoding technique makes it possible to form a Viterbi decoder for high code rate codes, and makes it possible to form a simple encoder/decoder which is capable of selecting the code rate.
If the puncturing codes are to be accurately decoded, a puncturing pattern synchronization has to be established between the transmitting part and the receiving part. However, the information on the puncture pattern synchronization is not transmitted, and therefore, the Viterbi decoder itself has to detect the puncture pattern synchronization based on the received codes so as to execute the decoding.
LSI Logic company adopted a method for detecting the puncture pattern synchronization in the following manner. That is, the bit error rate in the output of the Viterbi decoder in the puncture pattern non-synchronization status is higher than the puncture pattern synchronization status, and by utilizing this fact, the puncture pattern synchronization/non-synchronization is detected. The method the LSI Logic company had the disadvantage that the cost for hardware is increased due to the use of a convolution encoder and a buffer.